/**
 * DivisibleSetDiv2
 * 
 * difficuty:550
 * 
 * Statement 
You are given a int[] b containing a sequence of n positive integers: b[0], ..., b[n-1]. 
We are now looking for another sequence a[0], ..., a[n-1]. 
This sequence should have the following properties:

1 Each a[i] should be a number of the form 2^x[i] where x[i] is some positive integer. In other words, each a[i] is one of the numbers 2, 4, 8, 16, ...
2 For each i, the value a[i]^b[i] (that is, a[i] to the power b[i]) should be divisible by P, where P is the product of all a[i].

Determine whether there is at least one sequence with the desired properties. 
Return "Possible" (quotes for clarity) if such a sequence exists and "Impossible" otherwise.
 *
 * point:
 *   len = b.length;
 *   
 *   P = 2^len * xp
 *   
 *   2*x[i]*b[i] / P = N
 *   
 *   x[i]*b[i] / 2^(len-1) * xp =N
 *   
 *   b[i] = N * 2^(len-1) * xp / x[i];
 *   
 *   b[i]/2^(len-1) = N * xp / x[i] is Integer
 * 
 *   check every b[i]/2^(len-1) is Integer, that's ok.
 */
package org.yuwgle.srm.r697.d2;

public class DivisibleSetDiv2 {
	public static final String P = "Possible";
	public static final String I = "Impossible";
	
	public String isPossible(int[] b) {
		int len = b.length;
		double d = Math.pow(2, len-1);
		long pow = (long)d;
		
		for (int bi : b) {
			if (bi % pow != 0) {
				return I;
			}
		}
		return P;
	}
}
